/**
 * Copyright 厦门中软海晟信息技术有限公司 版权所有 违者必究 2019
 */
package com.leetCode;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;

/**
 * @author : sunzb(sunzb@hsit.com.cn)
 * @date: 2019/5/13
 */
public class _12_169_MajorityElement {

    public static int majorityElement4(int[] nums, int lo, int hi) {
        // base case; the only element in an array of size 1 is the majority
        // element.
        if (lo == hi) {
            return nums[lo];
        }
        // recurse on left and right halves of this slice.
        int mid = (hi-lo)/2 + lo;
        int left = majorityElement4(nums, lo, mid);
        int right = majorityElement4(nums, mid+1, hi);
        // if the two halves agree on the majority element, return it.
        if (left == right) {
            return left;
        }
        // otherwise, count each element and return the "winner".
        int leftCount = countInRange(nums, left, lo, hi);
        int rightCount = countInRange(nums, right, lo, hi);
        return leftCount > rightCount ? left : right;
    }

    private static int countInRange(int[] nums, int num, int lo, int hi) {
        int count = 0;
        for (int i = lo; i <= hi; i++) {
            if (nums[i] == num) {
                count++;
            }
        }
        return count;
    }

    public static int majorityElement3(int[] nums) {
        Arrays.sort(nums);
        return nums[nums.length/2];
    }

    public static int majorityElement2(int[] nums) {
        Arrays.sort(nums);
        int len = nums.length;
        if (len < 3) {
            return nums[0];
        }
        int midLen = len >> 1;
        int count = 0, value;
        for (int i = 0; i < len - 1; i++) {
            value = nums[i];
            if (nums[i + 1] == value) {
                count++;
            } else {
                count = 0;
            }
            if (count + 1 > midLen) {
                return value;
            }
        }
        return 0;
    }

    public static int majorityElement1(int[] nums) {
        Map<Integer, Integer> map = new HashMap<>();
        int len = nums.length;
        int midLen = len >> 1;
        int key;
        Integer value;
        for (int i = 0; i < len; i++) {
            key = nums[i];
            value = map.get(key);
            value = value == null ? 1 : value + 1;
            if (value > midLen) {
                return key;
            }
            map.put(key, value);
        }
        return 0;
    }

    public int majorityElement(int[] nums) {
        Map<Integer, Integer> map = new HashMap<>();
        int len = nums.length;
        int key;
        Integer value;
        for (int i = 0; i < len; i++) {
            key = nums[i];
            value = map.get(key);
            value = value == null ? 1 : value + 1;
            map.put(key, value);
        }
        int max = Integer.MIN_VALUE;
        int maxValue = Integer.MIN_VALUE;
        Iterator<Map.Entry<Integer, Integer>> iterator = map.entrySet().iterator();
        Map.Entry<Integer, Integer> next;
        while (iterator.hasNext()) {
            next = iterator.next();
            value = next.getValue();
            if (value > max) {
                max = value;
                maxValue = next.getKey();
            }
        }
        return maxValue;
    }

    public static void main(String[] args) {
//        System.out.println(majorityElement1(new int[] {2,2,1,1,1,2,2}));
//        System.out.println(majorityElement2(new int[] {2,2,1,1,1,2,2}));
//        System.out.println(majorityElement2(new int[] {1}));
//        System.out.println(majorityElement3(new int[] {2,2,1,1,1,2,2}));
//        System.out.println(majorityElement3(new int[] {1}));
        System.out.println(majorityElement4(new int[] {2,2,1,1,1,2,2}, 0, 6));
        System.out.println(majorityElement4(new int[] {1}, 0, 0));
    }
}
